In various applications it is necessary to find whether a given value is within a specified range or not. This computational problem is commonly known as “range matching” or “range querying.” Range matching is useful, for example, in communication packet analysis, packet routing, firewalls, Intrusion Detection Systems (IDS) and many other applications. Various range matching techniques are known in the art. For example, Zheng et al. describes techniques for finding all the keys in a certain range over an underlying Peer-to-Peer (P2P) network, in “Distributed Segment Tree: Support of Range Query and Cover Query over DHT,” Electronic publications of the 5th International Workshop on Peer-to-Peer Systems (IPTPS'06), 2006, which is incorporated herein by reference.
U.S. Pat. No. 7,394,809, whose disclosure is incorporated herein by reference, describes a packet classifier having a forest of hash tables. The forest of hash tables includes a number of hash tables, each hash table having a bit mask corresponding to an equivalent set of rules. Each hash table includes a number of entries, wherein an entry of a hash table may correspond to a rule. One or more of the hash tables may include a marker in one entry, wherein the marker identifies another one of the hash tables. The hash table identified by the marker is a descendant of the hash table in which the marker is placed.